import System.Random
import Data.List(tails)

data Code a = Single a | Multiple Int a deriving (Eq, Show, Read)

encodeModified :: (Eq a) => [a] -> [Code a]
encodeModified = foldr encode []
    where encode next []                       = (Single next) : []
	  encode next all@((Single x):xs)      = if x == next then (Multiple 2 x) : xs else (Single next) : all
	  encode next all@((Multiple n x):xs)  = if x == next then (Multiple (n+1) x) : xs else (Single next) : all

decodeModified :: (Eq a) => [Code a] -> [a]
decodeModified = foldr decode []
    where decode x xs = case x of
			    Single a     -> a:xs
			    Multiple n a -> (replicate n a) ++ xs


split :: (Eq a) => Int -> [a] -> ([a], [a]) 
split _ [] = ([], [])
split n xs = splitHE n ([], xs)
    where splitHE n (l, r@(y:ys)) | ys == [] = (l++[y], [])
				  | n >= 0 = splitHE (n-1) ( (l ++ [y]),ys)
				  | otherwise = (l, r)	


slice :: [a] -> Int -> Int -> [a]
slice xs (l+1) r | r < l     = xs
	         | otherwise = take (r-l) $ drop l xs 
				

rotate :: [a] -> Int -> [a]
rotate [] _ = []
rotate xs n = let len = length xs
		  sides = splitAt ((len+n) `mod` len) xs
	      in snd sides ++ fst sides

removeAt :: Int -> [a] -> (a, [a])
removeAt n xs = case back of
    []     -> error "index too large"
    x:rest -> (x, front ++ rest)
    where (front, back) = splitAt n xs
    
insertAt :: a -> [a] -> Int -> [a]
insertAt e xs (n+1) = front ++ e:back
    where (front, back) = splitAt n xs

range :: Int -> Int -> [Int]
range l r 
    | l <= r     = l : range (l+1) r
    | otherwise = [] 

rndSelect :: Int -> [a] -> IO [a]
rndSelect n xs = do
    gen <- newStdGen
    let inds = take n $ randomRs (0, (length xs) -1) gen :: [Int]
    return [xs !! p | p <- inds]

diffSelect :: Int -> Int -> IO [Int]
diffSelect n r = diffSelect' n [1..r]
    where diffSelect' 0 _  = return []
	  diffSelect' _ [] = error "you fucked it up!"
	  diffSelect' n xs = do m <- randomRIO (1, (length xs)-1)
			        let remaining = take m xs ++ drop (m+1) xs
				rest <- diffSelect' (n-1) remaining
				return ( (xs !! m) : rest)

rndPermu :: [a] -> IO [a]
rndPermu [] = return []
rndPermu xs = do m <- randomRIO (0, (length xs)-1)
		 let remaining = take m xs ++ drop (m+1) xs
		 rest <- rndPermu remaining
		 return ( (xs!!m) : rest)

combinations :: Int -> [a] -> [[a]]
combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

isPrime :: (Integral a) => a -> Bool
isPrime p = p > 1 && (all (\x -> p `mod` x /= 0) $ takeWhile (\x -> x*x <=p) [2..])
				
gcd' :: (Integral a) => a -> a -> a
gcd' a 0 = a
gcd' a b | a < 0     = gcd' (-a) b
	 | b < 0     = gcd' a (-b)
	 | b > a     = gcd' b a
	 | otherwise = let q = abs $ a `mod` b in gcd' b q

coprime :: (Integral a) => a -> a -> Bool
coprime a b = gcd a b == 1

totient :: (Integral a) => a -> Int
totient m = length [x | x <- [1..m-1], coprime m x]

primeFactors :: Int -> [Int]
primeFactors n = if length f > 0 then (head f) : (primeFactors (n `div` head f)) else [n]
    where f = [x | x <- 2:[3,5.. (n `div` 2)], n `mod` x == 0]
	  
